package leetcode.pre150;

import utils.TreeNode;

/**
 * 给定一个二叉树，找出其最小深度。
 * <p>
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * <p>
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 示例:
 * <p>
 * 给定二叉树 [3,9,20,null,null,15,7],
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回它的最小深度  2.
 *
 * @date 2020/6/2 12:38
 */
public class Code111_MinDepth_二叉树最小深度 {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        System.out.println(minDepth(treeNode));
    }
    /**
     *TODO BUG,【1，2】返回1，应该返回2.原因是1的右孩子为null但是递归了，返回0
     *TODO 和递归2返回1  取min是0.   事实上不应该去递归1的右孩子
     */
        public static int minDepth1(TreeNode root) {
        if(root == null) return 0;
        if(root.left == null && root.right == null)
            return 1;
        //如
        //   1
        // 2
        //当前节点root = 1,   root.right = null不应该递归，如果递归则返回0
        //root.left = 2,递归返回1
        int left = minDepth1(root.left);
        //事实上，root.right为null，不能继续递归
        int right = minDepth1(root.right);
        //此时右孩子返回0，左孩子返回1，所以取min是0。返回1
        return 1 + Math.min(left,right);

    }

    /**
     * @param root
     * @return
     */
    public static int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if ((root.left == null) && (root.right == null)) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;


        //root.left = 2 ，递归返回1
        if (root.left != null)
            min_depth = Math.min(minDepth(root.left), min_depth);
        //root.right == null，所以不递归
        if (root.right != null)
            min_depth = Math.min(minDepth(root.right), min_depth);

        //此时min_depth = min(1,MAX_VALUE)
        return min_depth + 1;
    }

}
